1. Field of the Invention
The present invention relates to networking of personal computing devices, and particularly to a method of forming a personal mobile grid system and resource scheduling thereon that provides for connecting all devices in a user's personal area network in a grid system for combining processing power and RAM or volatile memory when needed, and to an algorithm for resource sharing based upon the model of the honeybee that optimally allocates available resources in the grid when more computational power is need than is available on a single device in the grid.
2. Description of the Related Art
With the advent of cellular and wireless technologies, many users commonly utilize personal area networks (PANs), composed of multiple devices (such as cellular telephones, laptop computers with wireless connections, personal digital assistants (PDAs) and the like) that are able to communicate with each other through a network. Additionally, such personal area networks are often networked with additional devices, such as home or office computers, or mobile devices located in vehicles, to form personal networks (PNs).
PANs and PNs are most commonly used for applications involving data and peripheral sharing. This is due to the resources allowed for sharing in PNs, PANs and other conventional networks being limited to data, peripherals and secondary storage. The most important resources, namely, processor cycles and runtime memories, are presently not available for sharing across such networks. It would obviously be desirable to further enable these networks to seamlessly share other resources, such as processing cycles, storage capacity and functionality in the form of services available across computational grids. Since PNs can already share data, peripherals and secondary storage among their devices, the next logical step is to superimpose grid functionality over them to allow the sharing of processor cycles and memories. Thus, the net result is a huge virtual computer that can be accessed at anytime from anywhere.
Generally, two approaches have emerged in utilizing mobile devices in grid environments. In the first approach, mobile devices serve as interfaces to stationary grids in order to send requests and receive results. Thus, a mobile device is merely playing the role of a resource consumer. This approach is sometimes referred to as “mobile access to grid infrastructure” or a “Mobile Access Grid” (MAG). In the second approach, mobile devices actively participate in the grid by providing computational or data services. Thus, a mobile device can play the roles of both a resource provider and resource consumer. This approach is typically referred to as a “Mobile Grid” (MG).
In Mobile Grids and Mobile Access Grids, the mobile devices are commonly integrated with the grid infrastructure using a proxy between the stationary grid and mobile devices. Caches may be used to cope with the disconnectivity problem of mobile devices where operations on files are logged and then automatically applied when a client reconnects. In Mobile Ad hoc Grids (MAHGs), grid nodes usually exchange services in a pure peer-to-peer (P2P) scheme. This may be performed using intelligent agents or a mobile grid middleware system.
FIG. 2 illustrates the basic architecture of a typical PN. In the connectivity level (the lowest level shown in FIG. 2), devices are grouped into various radio domains based on their radio interfaces. A radio domain is a group of devices having a common radio interface and a single Medium Access Control (MAC) mechanism, and that are in direct communication range of each other. In the network level (the middle level in FIG. 2), devices within radio domains identified in the connectivity level are grouped into clusters based on a pre-established trust relationship. This trust relationship is very important to differentiate between personal nodes and devices and foreign nodes and devices. It is important to note that this trust relationship not only takes into account devices owned by the user, but also other devices with long-term trust relationships, such as family devices and devices from one's place of employment. The main function of this level is to separate communications among nodes of the same user from communications of other nodes. The service level is the highest level in the PN architecture. It contains all services offered by nodes in the Network Level. There are two types of services: public and private services. Public services are offered by both foreign and personal nodes and can be consumed by both. On the other hand, private services are offered and consumed by personal nodes only. While private services require establishing a long-term trust relationship, pubic services require a short-term trust relationship only. The service level contains all protocols related to service discovery and name servers.
A typical PN consists of a PAN, with the owner at its core. The PAN includes a set of personal nodes and devices around a person sharing a common trust relationship and communicating with others without relying on any foreign nodes or devices. The PN also includes clusters, PN nodes, PN devices, gateway nodes, a PN agent, and an interconnecting structure. A cluster is a set of personal nodes and devices that share a common trust relationship and can communicate with each other without relying on any foreign nodes or devices. In each cluster/PAN, PN nodes communicate with each other using the IP protocol. PN nodes have multiple air interfaces to connect to other PN nodes and devices. PN devices are devices that do not have IP capabilities. They are connected to other PN nodes and devices via a PN node. A personal node in a cluster/PAN does not operate in a stand-alone network. It needs to communicate with other nodes in remote clusters.
Therefore, a gateway node with special features and functionalities, such as local storage and multiple network interfaces, address translation, tunnels set up and maintenance, and traffic filtering, among others, is employed to link PN nodes to remote and foreign nodes. Gateway nodes are usually selected as powerful devices, as their tasks are quite load intensive. For gateway nodes to locate other gateway nodes in remote clusters and establish tunnels, the PN agent is used to provide additional services, such as naming and service discovery. The PN agent serves also as the entry point for PN to PN communication. It is important to add that the PN agent is not a device or node, rather it is a concept that might be implemented in different approaches. The interconnecting structure is typically a collection of overlapping networks of various technologies. A key element of a PN is the PN Provider (PNP), which offers the PN services. It provides the operational environment to manage users, services, content and network related issues.
In order for personal users to submit service requests (for example, a request for CPU cycles and memory to execute a computational job from any device available within their trusted PNs without being concerned about where, when or how these requests are executed), the grid network must utilize an efficient resource scheduler. The scheduler is responsible for automatically decomposing, allocating and executing jobs, and then finally composing final results, thus making them ready to the end user. The scheduler must preferably be lightweight, self-managed, and adaptive to cope with the dynamic nature of the grid environment.
In general terms, scheduling is a mechanism to allocate resources to jobs with the objective to optimize one or more performance measures. The mechanism belongs to a broader class of combinatorial search problems, which are concerned with finding combinations of a discrete set of items that satisfy some specified constraints. The number of possible combinations grows exponentially with the size of the problem, leading to potentially lengthy solution times and severely limiting the feasible size of such problems. Thus, scheduling is among the most difficult of common computational problems.
In reference to scheduling, a “resource” is anything that is required to carry on an operation, and includes such items as machines, processors and runways. A “job” is anything that consumes resources. A job usually consists of a single set of multiple tasks. A job can be a manufacturing process, a computer program, a landing or take-off, etc. A “task” is an atomic operation to be performed on a resource, and a “performance metric”, also known as the “objective function”, is the objective under consideration, such as the minimization of the makespan or maximization of the throughput. In essence, a schedule is a mapping between tasks and resources. With regard to the present system and method, the terms “resources” and “jobs” are mainly used to refer to resources and jobs associated with computers, such as processors and application programs.
Resource scheduling systems deal with four main entities: jobs, resources, performance metrics and a scheduler. In solving a scheduling problem, four questions are usually considered: How do resource characteristics affect the scheduling decision; how do job characteristics affect the scheduling decision; what performance measures should a scheduler use to determine the quality of a schedule; and which scheduler (policy, architecture and procedure) gives best (or good) results based on the previous three concerns?
The characteristics of underlying resources are critical for making a scheduling decision. For a scheduler to make a decision, it needs to know whether resources are of the same type or of different types, and the characteristics of each resource. Accordingly, two main resource models are commonly utilized: parallel and dedicated resources. Parallel resources are capable of performing the same functions. They are categorized further based on their speed as identical, uniform and unrelated resources. In contrast, dedicated resources are specialized in executing certain tasks only. Three distinguishable scheduling models are identified based on the order in which these tasks follow inside the system: flow shop, open shop and job shop scheduling models.
Identical resources are parallel resources with equal processing speeds. Uniform resources are parallel resources but with different processing speeds. However, the speed of each uniform resource is constant for all types of jobs. In contrast, each unrelated resource has a variant speed associated with each type of job. With regard to the flow shop, open shop and job shop scheduling models, these three scheduling models are based on the order in which jobs visit dedicated resources. In the flow shop scheduling model, each job is executed on all machines following a certain order. In the open shop model, each job is processed once on each machine with no constraint about the order of processing. In the job shop model, a job can be processed on more than one machine and has its own order in visiting machines.
The job model has a significant impact on the scheduling decision. For a scheduler to make a decision, it needs to know: The characteristics of each job in terms of its internal structure; and the amount and type of interaction it requires with other jobs or with the running environment. Based on this information, jobs are classified into two main categories: non-independent jobs and independent jobs. Dependent jobs, often referred to as “workflows”, are coarse-grained applications constructed from a sequence of components (i.e., tasks). Tasks themselves are considered heterogeneous in nature; they might be sequential or parallel having different behavior and resource requirements. Workflows vary in their internal structure, and there are two categories: directed acyclic graph (DAG) workflows and non-DAG workflows.
An independent job represents an application that is composed of a set of tasks having no communication, dependencies or synchronization among them. These tasks can be executed in any order since each task does not require any input from any other task. In other words, the output of any task would never be fed to another task as an input. However, multiple tasks can share the same input file(s) and they may also share the same output file(s). These applications are easy to parallelize by decomposing them into multiple tasks of lower granularity. From a theoretical perspective, an independent job model is a generalization of the pre-emptive execution model that allows for simultaneous execution of different parts of the same job on different machines. Applications conforming to this model arise in many fields of science and engineering, such as image processing, Monte Carlo simulations, data mining and database searching. There are two possible models for independent jobs based on the task granularity: Bag-of-Tasks (BoT) and Divisible Load (DL).
In DAG workflows, the internal structure of a workflow is represented by a DAG. Nodes of the graph represent tasks while edges represent dependencies between tasks. The simplest workflow applications can be represented with a simple DAG in which tasks are performed in a specific linear order. At the second level of complexity are workflows that are modeled using non-linear DAG. Some scientific applications require an iteration structure; in this case, workflows are modeled with cyclic graphs and are called non-DAG workflows. In the most complicated level of workflows, it is even difficult to find an appropriate graph model for the workflow. In this case, an application is modeled as a workflow of workflows.
Independent jobs can be composed of coarse-grained components, which are known as Bag-of-Tasks (BoT), or fine-grained components, which are known as Divisible Loads (DL). BoT jobs are also known as “parameter-sweep applications”. A BoT is a coarse-grained application consisting of computations that can be divided into a finite number of independent pieces (tasks). The number of tasks and the task size of each application are set in advance. In this case, the scheduling problem is normally considered as a bin packing problem. This problem is considered to be NP-hard and is usually approached by means of heuristics.
DL applications, also known as fine-grained applications, consist of computations or loads that can be arbitrarily divided into independent chunks (i.e., tasks). This corresponds to a perfectly parallel job: any task can itself be further decomposed into independent sub-tasks. A DL model is an approximation of job models that are built out of a large number of identical, low granularity components. This has the potential to provide a practical platform for scheduling in heterogeneous environments.
Performance metrics, also known as scheduling objectives, can be viewed from two different and competing perspectives: the user or consumer perspective (i.e., “job-centric” metrics) and the provider perspective (i.e., “resource-centric” metrics). Job-centric metrics represent the user or consumer perspective. They seek to optimize the performance of each individual job, such as the turnaround time (also known as “flow time”, “response time” or “completion time”), which represents the time taken from when a job enters the system until it finishes execution. Job-centric metrics are related to the system performance, which encompasses how well system resources are being used for the benefit of each user of the system.
Resource-centric metrics seek to optimize the system efficiency, such as throughput, resource utilization and makespan (i.e., the total time required for completing all jobs in a set). The system efficiency is concerned with how efficiently resources are utilized for the benefit of all users of the system, as well as the added overhead associated with the resource scheduling process. As job-centric and resource-centric metrics are competitive, there are always tradeoffs to consider. Therefore, hybrid approaches, such as economy-based metrics, have been utilized. Economy-based metrics consider both job (resource consumer) and resource (resource provider) perspectives at the same time, but from the market economy point of view. For the market to be competitive, resource providers need to set reasonable prices to keep the supply of a service equal to its demand. However, applying these metrics requires that the whole system is built initially with the economic model as a reference model.
A “scheduler model” describes the organization, policy and procedure of a resource scheduler. Scheduler “organization” refers to the way that entities involved in the scheduling process interact with each other. This organization has a critical influence on the efficiency of the scheduling process. In centralized schedulers, a single entity has the authority to make the scheduling decision; it makes the decision for the whole system regarding who should run what and when. This organization has the advantages of simplified management and deployment. Among the main disadvantages of such a scheduler are the lack of fault tolerance, poor scalability and difficulty in accommodating multiple policies. In decentralized schedulers, the scheduling authority is shared among the multiple entities of a resource management system. This organization eases scaling to large systems and is more fault tolerant if proper coordination is shouldered by the different schedulers.
In non-distributed schedulers, the responsibility for executing the scheduling policy physically resides in a single entity, whereas in distributed schedulers, this responsibility is shouldered by physically distributed entities. When the responsibility for making and carrying out policy decisions is shared among entities in a system, the scheduler is “distributed”. On the other hand, when the authority of making the scheduling decisions is distributed to the system entities, the scheduler is “decentralized”. Distributed schedulers can be classified further, based on the way an individual processor makes decisions, while executing the scheduling policy, into: cooperative and non-cooperative schedulers. In non-cooperative schedulers, individual entities act alone as autonomous agents and arrive at the scheduling decision independently of the action of other entities in the system. In cooperative schedulers, each entity has the responsibility to carry out its own portion of the scheduling task, but all entities are working toward a system wide goal.
A “scheduling policy” consists of a set of general features describing the scheduling process. Based on the way information about jobs and resources is generated, one can differentiate between deterministic and stochastic policies. In stochastic scheduling, job information, such as the processing time, is unknown in advance, but it is known to be a random selection of a given probability distribution. The actual information only becomes known when the processing has been completed. Stochastic scheduling is used where either the number of individuals is small or where there is reason to expect random events to have an important influence on the behavior of the system. Deterministic scheduling takes no account of random variation and therefore gives a fixed and precisely reproducible result, as opposed to stochastic scheduling, where different outcomes can result from the same initial conditions. However, it does not require that all job information is known in advance. Rather, it also considers problems where some job parameters are unknown in advance, such as non-clairvoyant and dynamic scheduling.
Among the significant factors that affect the scheduling decision are the volume and type of information available to the scheduler. Greater volumes of information about jobs, such as the number of jobs, their processing times and release dates can result in an optimum schedule. However, such information may not be available or may be too expensive to collect. Further, increasing the amount of information processed by a scheduler usually increases the time to produce a schedule. Therefore, two contrasting scheduling policies can be addressed based on the availability, or necessity, of such information: clairvoyant and non-clairvoyant scheduling.
In a clairvoyant scheduling policy, it is assumed that job characteristics, such as execution time and release dates, are available to the scheduler before the scheduling decision takes place; i.e., either before jobs enter the system (i.e., static scheduling) or just before starting their execution (i.e., dynamic scheduling). This assumption, however, is not valid for most real world processors. In contrast, a non-clairvoyant scheduling policy assumes and requires no prior knowledge about job or resource characteristics. This information might only be available after a job has been executed.
Within the realm of dynamic scheduling policies, two approaches can be identified based on when the scheduling decision takes place: immediate and batch policies. An immediate mode policy maps a job to a machine upon task arrival, whereas a batch mode scheduling policy is event driven. Thus, when a specified condition is satisfied, such as a certain number of tasks, or a time period elapsed, scheduling occurs. In an adaptive scheduling policy, the scheduling algorithm or parameters are dynamically modified according to the change in the system state. In a non-adaptive scheduling policy, the current system state has no influence on the scheduling policy. In a dynamic policy, part of the information about jobs and resources is revealed dynamically, thus schedules are generated in the same manner. However, this does not necessarily imply that the scheduling algorithm or parameters are dynamic as well, which is the case in adaptive scheduling policies.
In general, decisions about mapping tasks to resources can be made at two levels: the local level and global level. In a local scheduling policy, decisions are made based only on the job (sometimes a group of jobs or a sub-workflow) at hand. In a global scheduling policy, decisions are made based on all non-scheduled jobs (including jobs not yet started or the whole workflow). The main advantage of global policy schedulers, also known as “meta-schedulers”, is that they can provide a better overall result. On the other hand, making the scheduling decision takes a much longer time than with local policies. Thus, the overhead produced by a global policy can reduce the overall benefit and possibly exceed its benefits.
A schedule might offer the best performance for a job at its start but, over time, other jobs may introduce load into the system, or job requirements may change. To sustain good performance, high Quality of Service (QoS) and fault tolerance for long running jobs and real-time applications, schedulers usually include additional features, such as pre-emption, rescheduling, co-scheduling and resource reservation, to support such applications. A pre-emptive scheduling policy may block a job after it has started execution and resume it later on the same or a different machine. A rescheduling policy allows changing the machine on which a job is running (i.e., “migration”). It also allows swapping between jobs when a certain event occurs, such as new job arrival or machine down. In a co-scheduling policy, related jobs of an application are scheduled to run on different machines at the same time. Co-scheduling techniques rely on the communication behavior of the application to schedule the communicating jobs simultaneously. In a resource reservation policy, a job is allowed to reserve required resources even before having the job entering the system so it can ensure resource availability.
“Scheduling procedure” refers to the scheduling algorithm that implements the scheduling policy. Scheduling algorithms include both optimum and sub-optimum algorithms. An approximation algorithm uses the same formal computational model used by an optimum algorithm, but instead of searching the entire solution space for an optimum solution, the algorithm is satisfied when a “good” solution is found. This technique is used to decrease the time taken to find an acceptable solution (i.e., a schedule). In the case of heuristics, empirical data analysis is used to look for a “good” solution. A “heuristic” is a collection of rules or steps that guide one toward a solution that may or may not be optimal. Examples include greedy algorithms, Tabu search and simulated annealing. Approximation algorithms and heuristics are distinguished by performance guarantee and evaluation. An approximation algorithm usually has a theoretical performance guarantee; for example, the solution it calculates is ten percent worse than the best solution. On the other hand, a heuristic will usually have no performance guarantee, but its solution is intuitively close to the best solution.
A “grid” is a collection of computational resources that are coupled together to solve a single large problem that cannot be solved on any single one of these resources. Thus, a specialized resource management system must be employed to mitigate the complexity of managing such a large number of distrusted heterogeneous resources. Many current grid systems employ centralized schedulers to simplify the resource management process and ensure full control over resources. There are also hierarchical schedulers at several different layers with a grid scheduler (i.e., a “metascheduler”) at the highest level, a local scheduler (i.e., a “cluster scheduler”) at the lowest level, and other layers may exist in between. Both schemes are based on the assumption that a detailed system state is available to schedulers, which is highly expensive, considerably restricts the scalability of the system and generally unrealistic in many grid environments due to their dynamic nature.
Virtually all present grid systems employ clairvoyant scheduling policies assuming prior availability of information about incoming jobs, such as execution times and release dates. Additionally, static schedules are usually generated in advance, which is generally unrealistic in dynamic environments and severely restricts the system flexibility. Most grid resources are shared among several users or are available to grid usage only during idle cycles, dramatically affecting the predictability of resource availability. Grid computing applications are sometimes run in background mode or as a screen saver, only when the system is idle. In such a case, the resource is not “dedicated”, meaning that it is not exclusively devoted to grid utilization. A dedicated resource usually receives jobs from a single scheduler, in contrast to non-dedicated resources, which receive workloads from multiple schedulers.
In order to efficiently schedule a personal mobile grid, a resource scheduler should be self-scheduling and cooperative, in order to conceal the resource management complexity from the personal user, as well as being decentralized, local and adaptive, in order to cope with the highly dynamic environment, and should further be non-clairvoyant, in order to handle the unpredictability of incoming jobs.
Thus, a method of forming a personal mobile grid system and resource scheduling thereon solving the aforementioned problems is desired.